package Midium;

import java.util.HashMap;
import java.util.Map;


public class Solution538 {
    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public TreeNode convertBST(TreeNode root) {
        if (root == null) return null;
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        dfsCreateMap(root, map);
        dfsCreateSumTree(root, map);
        return root;
    }

    public static void dfsCreateMap(TreeNode root, Map<Integer, Integer> map) {
        map.put(root.val, 0);
        // 遍历map里已经有的数value，如果当前数val >= value ，则map对应的value+=val
        // 因为是二叉搜索树，所以采用左中右的顺序进行遍历
        //递归的看左子树
        if (root.left != null)
            dfsCreateMap(root.left, map);

        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            Integer value = entry.getKey();
            if (root.val >= value) {
                map.replace(entry.getKey(), entry.getValue() + root.val);
            }
        }

        //递归的看右子树
        if (root.right != null)
            dfsCreateMap(root.right, map);
    }

    public static void dfsCreateSumTree(TreeNode root, Map<Integer, Integer> map) {
        root.val = map.get(root.val);
        //递归的看左子树
        if (root.left != null)
            dfsCreateSumTree(root.left, map);
        //递归的看右子树
        if (root.right != null)
            dfsCreateSumTree(root.right, null);
    }
}
